#include "stream_reassembler.hh"

#include <algorithm>
#include <iostream>

// Dummy implementation of a stream reassembler.

// For Lab 1, please replace with a real implementation that passes the
// automated checks run by `make check_lab1`.

// You will need to add private members to the class declaration in `stream_reassembler.hh`

using namespace std;

StreamReassembler::StreamReassembler(const size_t capacity)
 : _next_index(0), _unassembled_bytes(0), _remains(capacity),
    _input(string(capacity, 0)), _input_right(0),
    _output(capacity), _capacity(capacity), _total_bytes(SIZE_MAX) {
    
 }

inline void StreamReassembler::_assemble_handler(const string &data, const size_t start, const size_t end) {
    // data实际需要写入的长度
    size_t &&realLen = end - start + 1;
    _output.write(data.substr(start, realLen));
    //_next_index += realLen;
    // 当所有的数据都已组装好时，关闭_output
    if(_output.bytes_written() >= _total_bytes)
        _output.end_input();
}

// index：data起始字符的abs_seqno；
// realIndex：data第一个需要插入的字符的abs_seqno；
// right：data最后一个需要插入的字符的abs_seqno（右闭）
size_t StreamReassembler::_unassemble_insert(const string &data, const size_t index, const size_t realIndex, size_t right) {
    size_t newAdd = 0, i = realIndex, ei = i % _capacity, insertCount = right - i + 1; // 插入数据长度
    // 从ei开始插，插到input末尾，能插多少字符
    size_t &&rightCount = _capacity - ei;
    // 第一个插入的字符在data中的索引
    size_t &&data_begin_index = i - index;
    if(insertCount > rightCount){
        string &&dataRightPart = data.substr(data_begin_index, rightCount);
        newAdd += count(_input.begin() + ei, _input.end(), 0);
        _input.replace(ei, rightCount, dataRightPart);

        size_t &&leftCount = insertCount - rightCount;
        newAdd += count(_input.begin(), _input.begin() + leftCount, 0);
        string &&dataLeftPart = data.substr(data_begin_index + rightCount, leftCount);
        _input.replace(0, leftCount, dataLeftPart);
    }else{
        newAdd += count(_input.begin() + ei, _input.begin() + ei + insertCount, 0);
        _input.replace(ei, insertCount, data.substr(data_begin_index, insertCount));
    }
    _unassembled_bytes += newAdd;
    auto iter = _interval_map.end();
//    size_t extras = newAdd > _remains? newAdd - _remains : 0;
//    if(!_interval_map.empty() && extras > 0) {
//        --iter;
//        // 有未组装的存在，并且有多余的，删除最后extras个
//        while (extras) {
//            size_t &&len = iter->second - iter->first + 1;
//            if (len <= extras) {
//                iter = _interval_map.erase(iter);
//                extras -= len;
//                --iter;
//                if(!extras) {
//                    _input_right = iter->second + 1;
//                    break;
//                }
//            } else {
//                _input_right = iter->second - extras + 1;
//                break;
//            }
//        }
//        if(iter->second >= i - 1 && iter->first < i){
//            i = max(_input_right, i) - 1;
//        }else
//            i = min(_input_right, i) - 1;
//    }else
//        // 有未组装的，且没有多余的
//        _input_right = max(_input_right, i--);

    if((iter = _interval_map.find(realIndex)) != _interval_map.end()){
        // 若已存在index开始的区间，更新右端点
        if(right > _interval_map[realIndex])
            _interval_map[realIndex] = right;
    }else{
        // 插入，返回插入的iter
        _interval_map.insert({realIndex, right});
        iter = _interval_map.find(realIndex);
    }

    _merge_helper(iter, right);

    return newAdd;
}

inline void StreamReassembler::_merge_helper(std::map<size_t, size_t>::iterator insertIter, const size_t right) {
    // 可能需要与之合并的上一个区间
    auto lastIter = insertIter != _interval_map.begin()? --insertIter : insertIter;
    auto iter = ++insertIter;
    while(iter != _interval_map.end() && iter->first <= right + 1) {
        if(iter->first <= lastIter->second + 1){
            // 如果iter与lastIter重叠或毗邻，则更新lastIter的右端点
            lastIter->second = max(lastIter->second, iter->second);
            iter = _interval_map.erase(iter);
        }else{
            lastIter = iter++;
        }
    }
}


//! \details This function accepts a substring (aka a segment) of bytes,
//! possibly out-of-order, from the logical stream, and assembles any newly
//! contiguous substrings and writes them into the output stream in order.
void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
    // data的右开
    _input_right = _output.bytes_read() + _capacity;
    size_t dataRight =
        min(index + data.size(), min(_total_bytes, _input_right));
//    cerr << "\ndataRight = " << dataRight << endl;
    // 若为最后一个段
    if (eof && _total_bytes == SIZE_MAX && index + data.size() <= _input_right)
        _total_bytes = dataRight;
    if(_output.bytes_written() >= _total_bytes)
        _output.end_input();
//    cerr << "\n--- push string -1\n";
    // 若data为空
    if(data.empty())
        return;
    // 改为右闭
    --dataRight;
    size_t next_index = _output.bytes_written();
//    cerr << "\n--- push string -2: index = " << index << ", dataRight = " << dataRight << ", next_index = " << next_index
//         << ", _input_right = " << _input_right << ", _total_bytes = " << _total_bytes << endl;
    // 截断，已组装的部分不要
    if(dataRight < next_index)
        return;
    size_t realIndex = max(index, next_index);
//    cerr << "\n--- push string -3\n";
    // 指数超出上限
    if (realIndex > dataRight)
        return;
    // 剩余容量
//    _remains = _capacity - unassembled_bytes() - _output.buffer_size();
//    // 无剩余容量
//    if (!_remains)
//        return;
    // data实际需要写入的大小
    size_t &&dataSize = data.size() - (realIndex - index);
//    cerr << "\n--- push string -4\n";
    // data为空时
    if (!dataSize)
        return;

    // 此刻，realIndex和dataRight在窗口的有效范围内
//    cerr << "\n--- ready to push string\n";

    if (next_index == realIndex && (_interval_map.empty() || dataRight < _interval_map.begin()->first - 1)) {
        // 如果_next_index == realIndex，且不与未组装的index最小的区间重叠/毗邻
        _assemble_handler(data, realIndex - index, dataRight - index);
    } else {
        // 插入区间
        _unassemble_insert(data, index, realIndex, dataRight);
        // 可能的话，再组装
        if (_interval_map.begin()->first == next_index) {
            // @TODO ？疑问：如果在收到最后一个分段之前 收到了一个右边界超过_total_bytes的分段（那个时候还不知道实际一共要收多少），但没有超出窗口界限，并且接下来将其组装了，怎么办？
            auto firstIter = _interval_map.begin();
            size_t &&len = min(firstIter->second + 1, _total_bytes) - next_index;
            size_t &&input_start = next_index % _capacity;
            string &&nextData = next_index + len - 1 < _input_right? _input.substr(input_start, len)
                                                                     : _input.substr(input_start, _input_right - next_index) + _input.substr(0, len - (_input_right - next_index));
            _assemble_handler(nextData, 0, len - 1);
            _unassembled_bytes -= firstIter->second - firstIter->first + 1;
            _interval_map.erase(firstIter);
        }
    }
}

size_t StreamReassembler::unassembled_bytes() const {
    return _unassembled_bytes;
}

bool StreamReassembler::empty() const {
    return unassembled_bytes() == 0;
}
